`
https://leetcode.cn/problems/number-of-matching-subsequences/
`

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var numMatchingSubseq = function (s, words) {
  // 记录 s 里面每个字符对应的出现位置索引
  const charToIdxs = {}
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    if (!charToIdxs[c]) {
      charToIdxs[c] = []
    }
    charToIdxs[c].push(i)
  }

  let res = 0

  // 依次遍历每个需要匹配的 word
  for (const word of words) {
    // i 表示在 word 上的指针
    let i = 0
    // j 表示在 s 上的指针
    let j = 0

    // 现在判断 word 是否是 s 的子序列
    // 借助 charToIdxs 查找 word 中每个字符在 s 中的索引
    while (i < word.length) {
      const c = word[i]
      // 如果 s 里面根本没有 c
      if (!charToIdxs[c]) {
        break
      }
      // 二分搜索大于等于 j 的最小索引
      // 即在 s[j..] 中搜索等于 word[i] 的最小索引
      const pos = leftBound(charToIdxs[c], j)
      // 如果没找到
      if (pos === charToIdxs[c].length) {
        break
      }
      // 更新 j 的位置
      j = charToIdxs[c][pos]
      // 如果找到，即 word[i] == s[j]，继续往后匹配
      i++
      j++
    }
    // 如果 word 完成匹配，则是 s 的子序列
    if (i === word.length) {
      res++;
    }
  }

  return res
};

function leftBound(arr, target) {
  let left = 0, right = arr.length - 1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return left
}